# /*
#  * @Author: TanFunWen 
#  * @Date: 2021-10-23 16:45:18 
#  * @Last Modified by:   TanFunWen 
#  * @Last Modified time: 2021-10-23 16:45:18 
#  */
# 找零兑换： 动态规划解法

def dpMakerChange(coinValueList, change, minCoins):
    for cents in range(change + 1):
        coinCount = cents
        for j in [c for c in coinValueList if c <= cents]:
            if minCoins[cents - j] + 1 < coinCount:
                coinCount = minCoins[cents - j] + 1
        minCoins[cents] = coinCount
    return minCoins[change]

if __name__ == "__main__":
    print(dpMakerChange([1,5,10], 21, [0]*22))